Exercici 2 (Tasca 6).
(R (decidable/recursive languages),
RE (semi-decidable/ recursively enumerable languages),
coRE)
Classificació II: llenguatges computables
Per a un nombre p, definim \mathcal L_p = \{x \mid M_p(x)\!\downarrow \text{ i accepta}\}. Per a cadascun dels llenguatges L següents, decidiu si L \in \mathbf{R}, L \in \mathbf{RE} \setminus \mathbf{R}, L \in \mathbf{coRE} \setminus \mathbf{R} o L \notin \mathbf{RE} \cup \mathbf{coRE}.
- \{p \mid \mathcal L_p \text{ és finit}\}
- \{p \mid \mathcal L_p \text{ és infinit}\}
- \{p \mid \mathcal L_p \text{ és incontextual}\}
- \{p \mid \mathcal L_p \text{ no és incontextual}\}